翻訳と辞書 Words near each other ・ "O" Is for Outlaw ・ "O"-Jung.Ban.Hap. ・ "Ode-to-Napoleon" hexachord ・ "Oh Yeah!" Live ・ "Our Contemporary" regional art exhibition (Leningrad, 1975) ・ "P" Is for Peril ・ "Pimpernel" Smith ・ "Polish death camp" controversy ・ "Pro knigi" ("About books") ・ "Prosopa" Greek Television Awards ・ "Pussy Cats" Starring the Walkmen ・ "Q" Is for Quarry ・ "R" Is for Ricochet ・ "R" The King (2016 film) ・ "Rags" Ragland ・ ! (album) ・ ! (disambiguation) ・ !! ・ !!! ・ !!! (album) ・ !!Destroy-Oh-Boy!! ・ !Action Pact! ・ !Arriba! La Pachanga ・ !Hero ・ !Hero (album) ・ !Kung language ・ !Oka Tokat ・ !PAUS3 ・ !T.O.O.H.! ・ !Women Art Revolution Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Stern-Brocot tree ： ウィキペディア英語版 Stern–Brocot tree In number theory, the Stern–Brocot tree is an infinite complete binary tree in which the vertices correspond one-for-one to the positive rational numbers, whose values are ordered from left to right as in a search tree. The Stern–Brocot tree was discovered independently by and . Stern was a German number theorist; Brocot was a French clockmaker who used the Stern–Brocot tree to design systems of gears with a gear ratio close to some desired value by finding a ratio of smooth numbers near that value. The root of the Stern–Brocot tree corresponds to the number 1. The parent-child relation between numbers in the Stern–Brocot tree may be defined in terms of continued fractions or mediants, and a path in the tree from the root to any other number ''q'' provides a sequence of approximations to ''q'' with smaller denominators than ''q''. Because the tree contains each positive rational number exactly once, a breadth first search of the tree provides a method of listing all positive rationals that is closely related to Farey sequences. ==A tree of continued fractions== Every positive rational number ''q'' may be expressed as a continued fraction of the form :$q\; =\; a\_0\; +\; \backslash cfrac\}\}\}\}=\; (a\_1,\; a\_2,\; \backslash ldots,\; a\_k)$ where ''k'' and ''a''0 are non-negative integers, and each subsequent coefficient ''ai'' is a positive integer. This representation is not unique because one has :$(a\_1,\; a\_2,\; \backslash ldots,\; a\_,\; 1)\; =\; (a\_1,\; a\_2,\; \backslash ldots,\; a\_+1)$ for every sequence of coefficients ''a''0, ..., ''a''''k''−1. Using this identity to rewrite any representation of the former form into the latter form, one may obtain that the final coefficient satisfies (unless , in which case one obtains ''a''0 ≥ 1); with this additional requirement the representation becomes unique. Then, unless , the number ''q'' has a parent in the Stern–Brocot tree given by the continued fraction expression :$(a\_1,\; a\_2,\; \backslash ldots,\; a\_k-1),$ which in case one can rewrite as $(a\_1,\; a\_2,\; \backslash ldots,\; a\_+1)$. For instance, the rational number has the continued fraction representation :$\backslash frac=1+\backslash cfrac1=\backslash frac.$ This parent is formed by decreasing the denominator in the innermost term of the continued fraction by 1, and contracting with the previous term if the fraction becomes $\backslash tfrac11$. Conversely each number ''q'' in the Stern–Brocot tree has exactly two children: if :$q\; =\; (a\_1,\; a\_2,\; \backslash ldots,\; a\_k)\; =\; (a\_1,\; a\_2,\; \backslash ldots,\; a\_k-1,1)$ then one child is the number represented by the continued fraction :$\backslash displaystyle\; (a\_1,\; a\_2,\; \backslash ldots,\; a\_k+1)$ while the other child is represented by the continued fraction :$(a\_1,\; a\_2,\; \backslash ldots,\; a\_k-1,2).$ One of these children is less than ''q'' and this is the left child; the other is greater than ''q'' and it is the right child (in fact the former expression gives the left child if ''k'' is odd, and the right child if ''k'' is even). For instance, the continued fraction representation of is () and its two children are () =  (the right child) and () =  (the left child). It is clear that for each finite continued fraction expression one can repeatedly move to its parent, and reach the root ()= of the tree in finitely many steps (in steps to be precise). Therefore every positive rational number appears exactly once in this tree. Moreover all descendants of the left child of any number ''q'' are less than ''q'', and all descendants of the right child of ''q'' are greater than ''q''. The numbers at depth ''d'' in the tree are the numbers for which the sum of the continued fraction coefficients is . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Stern–Brocot tree」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.